package org.xqh.study.leetcode.algorithm.studyplan;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName SortAlgorithm
 * @Description 排序算法
 * @Author xuqianghui
 * @Date 2021/3/25 9:18
 * @Version 1.0
 */
public class SortAlgorithm {

    public static void main(String[] args) {
//        int[] nums = {10, 5, 1, 9, 12, 22, 8, 3, 2, 100, 9, 13};
//        int[] nums = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5, 2, 11, 88, 11, 23};
        int[] nums = {5, 6, 9, 3, 1, 5, 2, 4, 7};
//        maoPao(nums);
//        choiceSort(nums);
//        shellSort(nums);
        quickSort(nums);
        System.out.println(JSON.toJSONString(nums));
    }

    /***
     * 冒泡排序 时间复杂度 O(n*n)
     * @param nums
     */
    public static void maoPao(int[] nums){
        int len = nums.length;
        for(int i = 0; i < len; i++){
            b: for(int j = len - 2; j >= 0; j--){
                if(nums[j+1] < nums[j]){
                    int rep = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = rep;
                }else if(j <= i){
                    break b;
                }
            }
        }
    }

    /**
     * 选择排序 O(n*n)
     * @param nums
     */
    public static void choiceSort(int[] nums){
        for(int i = 0; i < nums.length; i ++){
            int min = nums[i];
            int repIdx = i;
            for(int j = i + 1; j < nums.length; j++){
                if(nums[j] < min){
                    repIdx = j;
                    min = nums[j];
                }
            }
            if(repIdx != i){
                //交换位置
                nums[repIdx] = nums[i];
                nums[i] = min;
            }
        }
    }

    /**
     * 插入排序 时间复杂度 O(n*n)
     * @param nums
     */
    public static void insertSort(int[] nums){
        int len = nums.length;
        for(int i = 1; i < len; i++){
            for(int j = i - 1; j >= 0; j--){
                if(nums[j+1] < nums[j]){
                    int tmp = nums[j+1];
                    nums[j+1] = nums[j];
                    nums[j] = tmp;
                }else {
                    break;
                }
            }
        }
    }

    /**
     * 希尔排序  时间复杂度 O(n*(1.3~2))
     * @param nums
     */
    public static void shellSort(int[] nums){
        int len = nums.length;
        int mid = len / 2;
        while (mid >= 1){
            for(int i = 0; i < mid; i ++){
                //对 子数组 做 插入排序
                for(int j = i+mid; j < len; j+=mid){
                    c: for(int k = j - mid; k >= 0; k -= mid){
                        if(nums[k+mid] < nums[k]){
                            int tmp = nums[k+mid];
                            nums[k+mid] = nums[k];
                            nums[k] = tmp;
                        }else {
                            break c;
                        }
                    }
                }
            }
            mid = mid / 2;
        }
    }

    /**
     * 快速排序 O(n*logn)
     * @param nums
     */
    public static void quickSort(int[] nums){
        recursionQuickSort(0, nums.length - 1, nums);
    }

    public static void recursionQuickSort(int start, int end, int[] nums){
        if(start + 1 >= end){
            return ;
        }
        int comVal = nums[start];
        int kw = start;//替换坑位
        a:for(int i = end; i > start; i --){
            if(i == kw){
                break a;
            }
            if(comVal >= nums[i]){
                nums[kw] = nums[i];
                nums[i] = comVal;
                b:for(int j = kw + 1; j < i; j ++){
                    if(nums[j] > comVal){
                        //替换 坑位 i
                        nums[i] = nums[j];
                        nums[j] = comVal;
                        kw = j;
                        break b;
                    }
                }
            }
        }

        recursionQuickSort(start, kw, nums);
        recursionQuickSort(kw + 1, end, nums);
    }
}
